package com.zy.drug.controller;

import java.util.*;

public class Test2 {
    //  排序、字符串、数组、递归、栈（DFS BFS 哈希 队列 单调栈 滑动窗口 二分查找 并集 动态规划 双指针 进制转换 ）
    public static void levelOrderTraversal(TreeNode root) {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0; // 初始化层号为0

        while (!queue.isEmpty()) {
            int size = queue.size(); // 当前层的节点数
            System.out.print("Level " + level + ": ");
            while (size > 0) {
                TreeNode currentNode = queue.poll(); // 弹出当前节点
                System.out.print(currentNode.val + " "); // 打印当前节点的值
                if (currentNode.left != null) queue.offer(currentNode.left); // 左子节点入队
                if (currentNode.right != null) queue.offer(currentNode.right); // 右子节点入队
                size--;
            }
            level++; // 层号加1
            System.out.println(); // 换行准备输出下一层信息
        }
    }

//    public static void main(String[] args) {
//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);
//        root.left.left = new TreeNode(4);
//        root.left.right = new TreeNode(5);
//        root.right.left = new TreeNode(6);
//        root.right.right = new TreeNode(7);
//
//        levelOrderTraversal(root);
//    }

    public static void levelOrderTraversalTwo(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode currentNode = queue.poll(); // 访问节点并移除
            System.out.print(currentNode.val + " "); // 访问节点值
            if (currentNode.left != null) {
                queue.offer(currentNode.left); // 左子节点入队
            }
            if (currentNode.right != null) {
                queue.offer(currentNode.right); // 右子节点入队
            }
        }
    }
//
//    public static void main(String[] args) {
//        // 创建二叉树示例
//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);
//        root.left.left = new TreeNode(4);
//        root.left.right = new TreeNode(5);
//        root.right.left = new TreeNode(6);
//        root.right.right = new TreeNode(7);
//
//        // 执行层次遍历
//        levelOrderTraversalTwo(root); // 输出应为: 1 2 3 4 5 6 7
//    }

    // 二叉树 先序 中序 后序
    //先序遍历
    public void preOrder(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        System.out.print(treeNode.val);
        preOrder(treeNode.left);
        preOrder(treeNode.right);
    }

    //中序遍历
    public void midOrder(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        midOrder(treeNode.left);
        System.out.print(treeNode.val);
        midOrder(treeNode.right);
    }

    //后序遍历
    public void postOrder(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        postOrder(treeNode.left);
        postOrder(treeNode.right);
        System.out.print(treeNode.val);
    }

    //层次遍历
    public void cengOrder(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(treeNode);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            System.out.print(poll.val);
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
    }

    // 1-3
    public static void step(int n) {
        int step1 = 1, step2 = 1, step3 = 2;
        int step4 = n == 1 || n == 2 ? 1 : 2;
        for (int i = 4; i <= n; i++) {
            step4 = step3 + step1;
            step1 = step2;
            step2 = step3;
            step3 = step4;
        }
        System.out.println(step4);
    }

    public static int fn(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        return fn(n - 1) + fn(n - 3);
    }

//    public static void main(String[] args) {
////        int n = 7;
////        step(n);
////        System.out.println(fn(n));
//        testOderjinzhi();
//    }

    public static void testOder() {
        List<Integer> list = new ArrayList<>();
        list.add(2);
        list.add(4);
        list.add(5);
        list.add(1);
//        Arrays.sort;
//        Collections.sort(list);
        list.sort((h1, h2) -> {
            return h2 - h1;
        });
        for (Integer integer : list) {
            System.out.print(integer + ",");
        }
    }

    public static void testOderjinzhi() {
        int i = Integer.parseInt("110", 2);
        System.out.println(i);
        String s = Integer.toString(6, 2);
        System.out.println(s);
//        String.
    }

    // 二分查找方法，返回目标元素在数组中的索引，如果未找到则返回-1
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            // 计算中间索引，防止(left + right)过大导致溢出
            int mid = left + (right - left) / 2;

            // 检查中间元素是否是目标元素
            if (array[mid] == target) {
                return mid;
            }

            // 如果目标元素大于中间元素，则它必定在右半部分
            if (array[mid] < target) {
                left = mid + 1;
            } else { // 如果目标元素小于中间元素，则它必定在左半部分
                right = mid - 1;
            }
        }

        // 如果未找到目标元素，则返回-1
        return -1;
    }
    public static int seray(int[] array,int target){
        int left = 0;
        int right = array.length-1;
        while (left <= right){
            int mid = left + (right-left)/2;
            if(array[mid] == target){
                return mid;
            }
            if(array[mid] < target){
                left = mid +1;
            }else{
                right = mid -1;
            }
        }
        return -1;
    }

    // 测试方法
    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;
        int index = binarySearch(sortedArray, target);

        if (index != -1) {
            System.out.println("Element " + target + " found at index " + index);
        } else {
            System.out.println("Element " + target + " not found in the array");
        }
    }


}
